package com.cet.algorithm.回溯.数独问题;

import java.util.Arrays;

/**
 * @program: cet-practice
 * @description: 解数独
 * @author: 陈恩涛
 * @create: 2023-06-04 10:25
 **/
public class LC37 {

    public void solveSudoku(char[][] board) {
        backTracing(board);
    }

    public boolean backTracing(char[][] board) {

        // 递归终止条件

        // 递归逻辑
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    for (char k = '1'; k <= '9'; k++) {
                        if (isValid(board, i, j, k)) {
                            board[i][j] = k;
                            if (backTracing(board)) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int colum, char value) {

        // 检查列是否有重复
        for (int i = 0; i < board.length; i++) {
            if (board[i][colum] == value) {
                return false;
            }
        }

        // 检查行是否有重复
        for (int i = 0; i < board[0].length; i++) {
            if (board[row][i] == value) {
                return false;
            }
        }

        // 检查九宫格是否有重复
        // 值得学习

        int startRow = (row / 3) * 3;
        int startCol = (colum / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == value){
                    return false;
                }
            }
        }

        return true;
    }

    public static void main(String[] args) {
        LC37 lc37 = new LC37();
        char[][] board = new char[9][];

        board[0] = "53..7....".toCharArray();
        board[1] = "6..195...".toCharArray();
        board[2] = ".98....6.".toCharArray();
        board[3] = "8...6...3".toCharArray();
        board[4] = "4..8.3..1".toCharArray();
        board[5] = "7...2...6".toCharArray();
        board[6] = ".6....28.".toCharArray();
        board[7] = "...419..5".toCharArray();
        board[8] = "....8..79".toCharArray();

        lc37.solveSudoku(board);
        System.out.println(Arrays.deepToString(board));
    }
}
